package demo7;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-11
 * Time: 22:45
 */
public class TestDemo {

    //判断二叉树是不是完全二叉树（一般方法解决、递归套路解决）
    static class TreeNode{
        public int data;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int data){
            this.data = data;
        }
    }

    //信息表
    static class Info{
       public boolean isFull;
       public boolean isComplete;
       public int height;

       public Info(boolean isFull ,boolean isComplete,int height){
           this.isFull = isFull;
           this.isComplete = isComplete;
           this.height = height;
       }
    }

    public static boolean completeBinaryTree(TreeNode head){
        return process(head).isComplete;
    }

    public static Info process(TreeNode head){
        if(head==null) return new Info(true,true,0);

        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        //左树和右树中的最大值+1
        int height = Math.max(leftInfo.height,rightInfo.height)+1;

        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
        boolean isComplete = false;
        if(leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height){
            isComplete = true;
        } else if(leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height+1){
            isComplete = true;
        } else if(leftInfo.isComplete && rightInfo.isFull && leftInfo.height== rightInfo.height+1){
            isComplete = true;
        } else if(leftInfo.isFull && rightInfo.isComplete && leftInfo.height== rightInfo.height+1){
            isComplete = true;
        }

        return new Info(isFull,isComplete,height);
    }



}
